package me.eg.night;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 *
 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
 *
 * 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
 *
 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
 */
public class FindAnagrams {
    /**
     * 解法：字符串排序 + 哈希
     * leetcode上超时
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        char[] pchars = p.toCharArray();
        Arrays.sort(pchars);
        long hash = calcHash(pchars);
        int m = p.length();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < s.length() - m + 1; i++) {
            char[] chars = s.substring(i, i + m).toCharArray();
            Arrays.sort(chars);
            if(calcHash(chars) == hash) ans.add(i);
        }
        return ans;
    }

    private long calcHash(char[] chars) {
        int b = 131, p = (int) 1e9 + 1;
        long hash = 0;
        for (int i = 0; i < chars.length; i++) {
            hash = (hash * b + (chars[i] - 'a' + 1)) % p;
        }
        return hash;
    }

    /**
     * 解法：字符串计数 + 哈希
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams_1(String s, String p) {
        char[] pchars = p.toCharArray();
        int[] cnt = count(pchars);
        long hash = calcHash(cnt);
        int m = p.length();
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < s.length() - m + 1; i++) {
            char[] chars = s.substring(i, i + m).toCharArray();
            if(calcHash(count(chars)) == hash) ans.add(i);
        }
        return ans;
    }

    private int[] count(char[] chars) {
        int[] cnt = new int[26];
        for (int i = 0; i < chars.length; i++) {
            cnt[chars[i] - 'a']++;
        }
        return cnt;
    }

    private long calcHash(int[] cnt) {
        int b = 131, p = (int) 1e9 + 1;
        long hash = 0;
        for (int i = 0; i < cnt.length; i++) {
            if (cnt[i] == 0) continue;
            hash = (hash * b * b + i * b + cnt[i]) % p;
        }
        return hash;
    }

    /**
     * 解法：滑动窗口计数
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams_2(String s, String p) {
        List<Integer> ans = new ArrayList<>();

        int n = s.length();
        int m = p.length();
        if (n < m) return ans;

        int[] scnt = new int[26];
        int[] pcnt = new int[26];
        for (int i = 0; i < m; i++) {
            scnt[s.charAt(i) - 'a']++;
            pcnt[p.charAt(i) - 'a']++;
        }

        if (Arrays.equals(scnt, pcnt)) ans.add(0);


        for (int i = 1; i < n - m + 1; i++) {
            scnt[s.charAt(i - 1) - 'a']--;
            scnt[s.charAt(i + m - 1) - 'a']++;
            if(Arrays.equals(scnt, pcnt)) ans.add(i);
        }
        return ans;
    }
}
